#include "common.h"
#include <queue>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
    ListNode *merge(const vector<ListNode *>::iterator &begin, const vector<ListNode *>::iterator &end)
    {
        ptrdiff_t count = std::distance(begin, end); // 计算当前范围内的链表数量
        if (count == 0)
        {
            return nullptr;
        }
        if (count == 1)
        {
            return *begin;
        }
        auto mid = begin + (count >> 1);
        ListNode *l1 = merge(begin, mid);
        ListNode *l2 = merge(mid, end);

        return mergeList(l1, l2);
    }
   ListNode *mergeList(ListNode *l1, ListNode *l2)
    {
        if (!l1)return l2;
        if (!l2)return l1;

        ListNode *dummyHead, *cur;
        dummyHead = new ListNode;
        dummyHead->next = nullptr;
        cur = dummyHead;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                cur = cur->next = l1;
                l1 = l1->next;
            }
            else
            {
                cur = cur->next = l2;
                l2 = l2->next;
            }
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }


public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        return merge(lists.begin(), lists.end());
    }
};

class Solution
{
private:
    struct cmp
    {
        bool operator()(ListNode *l1, ListNode *l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<ListNode *, vector<ListNode *>, cmp> heap;
        for (auto l : lists)
        {
            if (l)
                heap.push(l);
        }
        ListNode *ret = new ListNode;
        ListNode *cur = ret;
        while (!heap.empty())
        {
            ListNode *tmp = heap.top();
            heap.pop();
            cur->next = tmp;
            cur = tmp;
            if (tmp->next)
                heap.push(tmp->next);
        }
        cur = ret->next;
        delete ret;
        return cur;
    }
};

class Solution
{
    struct cmp
    {
        bool operator()(ListNode *l1, ListNode *l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<ListNode *, vector<ListNode *>, cmp> heap;

        // 链表进入小根堆
        for (auto l : lists)
            if (l)
                heap.push(l);

        // 合并
        ListNode *newhead = new ListNode;
        ListNode *prev = newhead;
        while (!heap.empty())
        {
            auto t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if (t->next)
                heap.push(t->next);
        }
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};